package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;
import org.apache.commons.lang3.StringUtils;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @link main.java.leecode.tree.langbuladong.Solution297
 * void traverse(TreeNode root) {
 *     if (root == null) return;
 *     // 初始化队列，将 root 加入队列
 *     Queue<TreeNode> q = new LinkedList<>();
 *     q.offer(root);
 *
 *     while (!q.isEmpty()) {
 *         TreeNode cur = q.poll();
 *System.out.println(root.val);
 * if(cur.left!=null){
 * q.offer(cur.left);
 * }
 * if(cur.right!=null){
 * q.offer(cur.right);
 * }
 * }
 * }
 *
 * 使用层级遍历的方式完成
 */
public class Solution297_2 {
    // Encodes a tree to a single string.
    // 层级遍历
    StringBuffer sb = new StringBuffer();

    public String serialize(TreeNode root) {
        if (root ==null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            if (treeNode ==null) {
                sb.append("#").append(",");
                continue;
            }
            sb.append(treeNode.val).append(",");
            queue.offer(treeNode.left);
            queue.offer(treeNode.right);
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 层级遍历 第一个元素为 头元素
        if (StringUtils.isEmpty(data)) {
            return null;
        }
        String[] split = data.split(",");
        String rootval = split[0];
        TreeNode rootNode = new TreeNode(Integer.parseInt(rootval));
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(rootNode);
        for (int i=1;i<split.length ;) {
            TreeNode parentNode = queue.poll();
            String s = split[i++];
            if ("#".equals(s)){
                parentNode.left = null;
            }else {
                parentNode.left = new TreeNode(Integer.parseInt(s));
                queue.offer(parentNode.left);
            }
            // 右边的节点数据
            String right = split[i++];
            if ("#".equals(right)){
                parentNode.right = null;
            }else {
                parentNode.right = new TreeNode(Integer.parseInt(right));
                queue.offer(parentNode.right);
            }


        }

        return rootNode;
    }

    @Test
    public void test(){
        TreeNode treeNode = new TreeNode(0);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode.left=treeNode1;
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.right=treeNode4;
        treeNode.right = treeNode5;
        String serialize = this.serialize(treeNode);
        System.out.println(serialize);

        TreeNode deserialize = this.deserialize(serialize);
        System.out.println(deserialize);
    }

}
